// https://leetcode.cn/problems/maximum-subarray/description/


// 以i位置的元素结尾的连续数组能获得的最大的值

function maxSubArray(nums: number[]):number {
    const n = nums.length;
    // 1.定义状态
    const dp: number[] = [];
    // 2.初始化状态
    dp[0] = nums[0];
    // 3.状态转移方程
    for(let i = 1; i < n; i++) { 
        // 拿到当前数组的值和之前的最大值，如果之前的最大值是正数，则将当前值和之前的值进行相加，
        // 如果之前是负的，则当前值就是当前位置的最大连续数组的和,因为当前值也有可能是负的，所以选出更大的值更严谨
        dp[i] = Math.max(nums[i] + dp[i - 1] , nums[i]);
    }
    // console.log(dp)
    // 4.返回出结果
    return Math.max(...dp);
}
console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))

export default {};